#include <iostream>
#include <vector>
#include <string>


using namespace std;




//BFS解决最短路问题：为高尔夫比赛砍树（解法优化）
class SolutionX {
private:
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    int cutOffTree(vector<vector<int>>& f) 
    {
        m=f.size();n=f[0].size();
        vector<vector<int>> trees;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(f[i][j]>1)
                    trees.push_back({f[i][j],i,j});
            }
        }
        sort(trees.begin(),trees.end());

        int ret=0;
        int bx=0;int by=0;
        for(int i=0;i<trees.size();i++)
        {
            int path=bfs(f,bx,by,trees[i][1],trees[i][2]);
            if(path==-1)    return -1;
            else    ret+=path;
            bx=trees[i][1];
            by=trees[i][2];
        }
        return ret;
    }

    int bfs(vector<vector<int>>& f,int bx,int by,int ex,int ey)
    {
        if(bx==ex&&by==ey)    return 0;
        int path=0;
        bool check[51][51]={};
        queue<pair<int,int>> q;
        q.push({bx,by});
        check[bx][by]=true;
        while(!q.empty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                auto top=q.front();
                q.pop();
                if(top.first==ex&&top.second==ey)
                {
                    return path;
                }   
                for(int j=0;j<4;j++)
                {
                    int x=top.first+dx[j];
                    int y=top.second+dy[j];
                    if(x>=0&&y>=0&&x<m&&y<n&&check[x][y]==false&&f[x][y]!=0)
                    {
                        q.push({x,y});
                        check[x][y]=true;
                    }
                }
            }
            path++;
        }
        return -1;
    }
};




//BFS多源问题01：矩阵
class Solution1
 {
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) 
    {
        m=mat.size();n=mat[0].size();
        vector<vector<int>> dist(m);
        queue<pair<int,int>> q;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    dist[i].push_back(0);
                    q.push({i,j});
                }
                else
                    dist[i].push_back(-1);     
            }
        }
        while(!q.empty())
        {
            auto top=q.front();
            q.pop();
            for(int j=0;j<4;j++)
            {
                int x=dx[j]+top.first;
                int y=dy[j]+top.second;
                if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1)
                {
                    dist[x][y]=dist[top.first][top.second]+1;
                    q.push({x,y});
                }
            }
        }
        return dist;
    }
};


//BFS多源问题02：飞地的数量
class Solution2 {
    int m, n;
    //bool memo[501][501]={};
    int dx[4]={0,0,-1,1};
    int dy[4]={-1,1,0,0};
public:
    int numEnclaves(vector<vector<int>>& grid) 
    {
        int ret=0;
        m = grid.size();
        n = grid[0].size();
        queue<pair<int, int>> q;
        for(int i=0;i<m;i++)
        {
            if(grid[i][0]==1)
            {
                q.push({i,0});
                grid[i][0]=-1;
            }
                //bfs(grid,i,0);
            if(grid[i][n-1]==1)
            {
                q.push({i,n-1});
                grid[i][n-1]=-1;
            }
                //bfs(grid,i,n-1);  
        }
        for(int j=0;j<n;j++)
        {
            if(grid[0][j]==1)
            {
                q.push({0,j});grid[0][j]=-1;
            }
                //bfs(grid,0,j);
            if(grid[m-1][j]==1)
            {
                q.push({m-1,j});grid[m-1][j]=-1;
            }
                //bfs(grid,m-1,j);  
        }

        while(!q.empty())
        {
            auto [a,b]=q.front();
            q.pop();
            //grid[a][b]=-1;
            for(int k=0;k<4;k++)
            {
                int x=a+dx[k];
                int y=b+dy[k];
                if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1)
                {
                    //cout<<x<<":"<<y<<" ";
                    q.push({x,y});
                    grid[x][y]=-1;
                }
            }
        }
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(grid[i][j]==1)
                    ret++;
        return ret;
    }
};



int mian()
{
    return 0;
}